package com.shuang.dp1;

public class Solution {

//
//    //动态规划 dp数组
//    public int fib(int n) {
//
//        if (n < 2){
//            return n;
//        }
//
//        //dp数组dp[i]为序列第i个数
//        int[] dp = new int[n + 1];
//        //递归公式dp[i] = dp[i-1] + dp[i-2]
//
//        //初始化dp数组
//        dp[0] = 0;
//        dp[1] = 1;
//
//        //由递归公式知道 遍历顺序要从前向后遍历
//        for (int i = 2; i <= n; i++){
//            dp[i] = dp[i - 1] + dp[i - 2];
//        }
//
//        return dp[n];
//    }

    //动态规划 dp数组
    public int fib(int n) {

        if (n < 2){
            return n;
        }

        //dp数组只需要维护两个数即可 dp[1]是最后一个数Fn dp[0]是前一个数Fn-1
        int[] dp = new int[2];
        //递归公式dp[i] = dp[i-1] + dp[i-2]

        //初始化dp数组
        dp[0] = 0;
        dp[1] = 1;


        //由递归公式知道 遍历顺序要从前向后遍历
        for (int i = 2; i <= n; i++){

            int sum = dp[0] + dp[1];

            dp[0] = dp[1];

            dp[1] = sum;


        }

        return dp[1];
    }


}
